package util;

import java.math.BigInteger;

/**
 * @author Egor Kulikov (kulikov@devexperts.com)
 */
class NumberUtil {
	public static class BooleanHolder {
		public boolean value = false;

		public BooleanHolder() {
		}

		public BooleanHolder(boolean value) {
			this.value = value;
		}
	}

	public static long power(int base, int exponent, int mod) {
		if (exponent == 0)
			return 1;
		long power = power(base, exponent >> 1, mod);
		power *= power;
		power %= mod;
		if ((exponent & 1) != 0) {
			power *= base;
			power %= mod;
		}
		return power;
	}

	public static long[][] binomialCoefficients(int size) {
		long[][] c = new long[size][size];
		for (int i = 0; i < size; i++) {
			c[i][0] = 1;
			for (int j = 1; j <= i; j++)
				c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
		return c;
	}

	public static BigInteger[] fundamentalPellSolution(long n) {
		long a0 = (long) (Math.sqrt(n) + 1e-8);
		if (a0 * a0 == n)
			return null;
		long m = 0;
		long d = 1;
		long a = a0;
		BigInteger lastP = BigInteger.ONE;
		BigInteger lastQ = BigInteger.ZERO;
		BigInteger p = BigInteger.valueOf(a0);
		BigInteger q = BigInteger.ONE;
		BigInteger bigN = BigInteger.valueOf(n);
		while (true) {
			m = d * a - m;
			d = (n - m * m) / d;
			a = (a0 + m) / d;
			BigInteger bigA = BigInteger.valueOf(a);
			BigInteger nextP = lastP.add(p.multiply(bigA));
			BigInteger nextQ = lastQ.add(q.multiply(bigA));
			lastP = p;
			lastQ = q;
			p = nextP;
			q = nextQ;
			if (p.multiply(p).subtract(q.multiply(q).multiply(bigN)).equals(BigInteger.ONE))
				return new BigInteger[]{p, q};
		}
	}

	public static int gcd(int a, int b) {
		while (b != 0) {
			int t = a % b;
			a = b;
			b = t;
		}
		return a;
	}	
}
